package offer;

public class offer_0012 {
    public boolean exist(char[][] board, String word) {
        int m=board.length;
        int n=board[0].length;
        int[][]  path=new int[m][n];
        boolean[] flag = new boolean[1];
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                search(board,path,flag,word,0,i,j,m,n);
            }
        }
        return flag[0];
    }
    public void search(char[][] board,int[][]  path,boolean[] flag,String word,int index,int i,int j,int m,int n){
        if(index==word.length()){
            flag[0]=true;
            return;
        }
        if(i<m&&i>=0&&j<n&&j>=0&&path[i][j]==0){
            if(word.charAt(index)==board[i][j]){
                path[i][j]=1;
                search(board, path, flag, word, index+1, i+1, j, m, n);
                search(board, path, flag, word, index+1, i, j+1, m, n);
                search(board, path, flag, word, index+1, i-1, j, m, n);
                search(board, path, flag, word, index+1, i, j-1, m, n);
                path[i][j]=0;
            }
        }
    }
}
